#include <vector>
using std::vector;

//根据中位数定理，奇数为中间值，偶数为两个平均值
//可以转化成寻找两个有序数组中的第 k 小的数

class Solution {
public:
    int findNum(vector<int>& nums1, vector<int>& nums2, int k) {
        int size_1 = nums1.size();
        int size_2 = nums2.size();
        int index_1 = 0, index_2 = 0;

        while (true) {
            if (index_1 == size_1)
                return nums2[index_2 + k - 1];
            if (index_2 == size_2)
                return nums1[index_1 + k - 1];
            if (k == 1)
                return __min(nums1[index_1], nums2[index_2]);

            int newIndex_1 = __min(index_1 + k / 2 - 1, size_1 - 1);
            int newIndex_2 = __min(index_2 + k / 2 - 1, size_2 - 1);
            int value_1 = nums1[newIndex_1];
            int value_2 = nums2[newIndex_2];
            if (value_1 <= value_2) {
                k -= newIndex_1 - index_1 + 1;
                index_1 = newIndex_1 + 1;
            } else {
                k -= newIndex_2 - index_2 + 1;
                index_2 = newIndex_2 + 1;
            }
        }
    }

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int length = nums1.size() + nums2.size();
        if (length % 2 == 1)
            return findNum(nums1, nums2, (length + 1) / 2);
        else
            return (findNum(nums1, nums2, length / 2) + findNum(nums1, nums2, length / 2 + 1)) / 2.0;
    }
};